﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
using CubeDetection;

namespace CubeCalculations
{
   public class ThreadedEvolutionaryCubexSolutionTree
   {
      private readonly Cubex BaseCube;
      private readonly ThreadedEvolutionaryCubexWorker[] CubexWorker;
      private readonly Thread[] CubexWorkerThread;
      private Thread MainWorkerThread;
      private readonly Random random;
      private readonly Dictionary<List<int>, float> SolutionList = new Dictionary<List<int>, float>();
      private readonly Queue<List<int>> SolutionQueue = new Queue<List<int>>();
      private readonly ManualResetEvent ResetEvent = new ManualResetEvent(false);
      private const int ThreadCount = 2;
      private readonly MovementRating MovementRating = new MovementRating();

      public delegate void SetSolutionEventHandler(List<int> Solution, float SolutionBefore, float SolutionImprovement);

      //public delegate void StatusUpdateEventHandler(float Percent, float Steps,float ImprovementPercent);

      public event StatusUpdateEventHandler OnStatusChanged;

      private void InvokeOnStatusChanged(float Percent, float Steps, float ImprovementPercent)
      {
         StatusUpdateEventHandler Handler = OnStatusChanged;
         if (Handler != null) Handler(Percent, Steps, ImprovementPercent);
      }

      private void InvokeOnStatusChanged(float Percent, float Steps)
      {
         StatusUpdateEventHandler Handler = OnStatusChanged;
         float ImprovementPercent = (RootElement == null)
                                       ? 0f
                                       : 100f - ((float) OverAllSolutionLength/(float) RootElement.Fitness*100f);
         if (Handler != null) Handler(Percent, Steps, ImprovementPercent);
      }


      public event SetSolutionEventHandler OnSetSolution;

      private void InvokeOnSetSolution(List<int> Solution, float SolutionBefore, float SolutionImprovement)
      {
         SetSolutionEventHandler Handler = OnSetSolution;
         if (Handler != null) Handler(Solution, (RootElement == null) ? 1f : RootElement.Fitness, SolutionImprovement);
      }


      public ThreadedEvolutionaryCubexSolutionTree()
      {
         BaseCube = new Cubex();
         random = new Random((int) DateTime.Now.Ticks);


         CubexWorker = new ThreadedEvolutionaryCubexWorker[ThreadCount];
         CubexWorkerThread = new Thread[ThreadCount];

         for (int i = 0; i < CubexWorker.Length; i++)
         {
            CubexWorker[i] = new ThreadedEvolutionaryCubexWorker();
            CubexWorker[i].OnRequestMoves += OnRequestMoves;
            CubexWorker[i].OnSetSolution += ThreadOnSetSolution;
            CubexWorkerThread[i] = new Thread(CubexWorker[i].EvaluateSolutions) {IsBackground = true};
            CubexWorkerThread[i].Start();
         }
      }

      public Cubex Cube
      {
         get { return BaseCube; }
         set
         {
            value.CopyTo(BaseCube);
            //foreach (ThreadedEvolutionaryCubexWorker cubexWorker in CubexWorker)
            //{
            //   cubexWorker.Cube = value;
            //}
         }
      }

      public List<CubeMoves> SolveCube()
      {
         BaseCube.SolveCube();
         return BaseCube.Solution();
      }



      public bool GetNextChild(BTElement RootElement, out BTElement CurrentElement)
      {
         if (!RootElement.Evaluated)
         {
            CurrentElement = RootElement;
            return true;
         }
         foreach (var child in RootElement.Childs.Values)
         {
            if (!child.Evaluated)
            {
               CurrentElement = child;
               return true;
            }
            if (GetNextChild(child, out CurrentElement))
               return true;
         }
         CurrentElement = null;
         return false;
      }


      //BacktrackingPoint btPoint = new BacktrackingPoint();
      //private BacktrackingList currentBTPointList;
      //private float CurrentSolutionToImprove;
      private float OverAllSolutionLength;
      private List<int> OverAllSolution;
      private BTElement RootElement;
      private BTElement CurrentElement;
      private int SolutionsToCalc, SolutionsCalculated; 
      int TrySolution = 60;

      private void EvaluateSolution()
      {
         lock (this)
         {
            IsActive = true;
         }

         DebugOut.Reset();
         OverAllSolution = new List<int>();
         SolutionsToCalc = TrySolution;
         SolutionsCalculated = 0;

         RootElement= new BTElement();
         RootElement.Fitness = OverAllSolutionLength = MovementRating.RateSolution(BaseCube);
         CurrentElement = RootElement;

         InvokeOnStatusChanged(0f, RootElement.Fitness,0f);

         //BestSolutionLength = int.MaxValue;

         const int MinMoves = 1;
         const int MaxMoves = 7;
         
         while(GetNextChild(RootElement,out CurrentElement) && !interrupt)
         {
            //Generiere Neue Lösungen und behalte bestes
            PrepareCube(BaseCube, CurrentElement.Solution);


            for (int i = 0; i < TrySolution; i++)
            {
               var List = new List<int>();
               int MoveCount = random.Next(MinMoves, MaxMoves);
               for (int k = 0; k < MoveCount; k++)
               {
                  List.Add(random.Next(0, BaseCube.CubeRotation.Length));
               }
               SolutionQueue.Enqueue(List);
            }
            TrySolution = 20;
            //Threads Starten
            ResedFinished();
            foreach (ThreadedEvolutionaryCubexWorker cubexWorker in CubexWorker)
            {
               cubexWorker.Continue();
            }

            //Auf beendigung warten
            ResetEvent.Reset();
            ResetEvent.WaitOne();

            if (CurrentElement == RootElement)
               RootElement.Childs.RemoveAll(5);
            CurrentElement.Evaluated = true;

            InvokeOnStatusChanged((float)SolutionsCalculated / (float)SolutionsToCalc * 100f, OverAllSolutionLength);
            DebugOut.Output("Anotherone finished!");
         }

         //Cubex solutionCube = new Cubex();
         //PrepareCube(BaseCube, solutionCube, PreSolutionList);
         //int SolutionLen = SolveCube(solutionCube, PreSolutionList.Count);
         //float SolutionImprovement = SolutionLen - BaseSolution;

         InvokeOnSetSolution(OverAllSolution, 0, 0);
         lock (this)
         {
            IsActive = false;
         }
      }


      //List<int> FindBestSolution()
      //{
      //   var SolutionList = new List<int>();

      //   BTElement Fittest;
      //   if (!FindBetterSolution(RootElement, RootElement.Fitness, out Fittest))
      //      Fittest = RootElement;
      //   do
      //   {
      //      SolutionList.InsertRange(0, Fittest.Solution);
      //   } while ((Fittest = Fittest.Parent) != null);
      //   return SolutionList;
      //}
   










      //////////private List<int> PreSolutionList;
      //////////private void EvaluateSolution()
      //////////{
      //////////   lock (this)
      //////////   {
      //////////      IsActive = true;
      //////////   }




      //////////   //neuer BT Versuch
      //////////   currentBTPointList = btPoint.BackTrackingList;








      //////////   //btList.Clear();

      //////////   float BaseSolution = MovementRating.RateSolution(BaseCube);
      //////////   //int BaseSolution = SolveCube(BaseCube);
      //////////   InvokeOnStatusChanged(0f, BaseSolution);
      //////////   PreSolutionList = new List<int>();

      //////////   float OverAllSolutionLength = BaseSolution, NoImprovementCount = 0;
      //////////   BestSolutionLength = int.MaxValue;

      //////////   int MinMoves = 1, btMin = 1, MaxMoves = 7, btMax = 5;

      //////////   int next = 12;
      //////////   for (int j = 0; j < next; j++)
      //////////   {
      //////////      //Generiere Neue Lösungen und behalte bestes
      //////////      PrepareCube(BaseCube, PreSolutionList);

      //////////      for (int i = 0; i < 50; i++)
      //////////      {
      //////////         var List = new List<int>();
      //////////         int MoveCount = random.Next(MinMoves, MaxMoves);
      //////////         for (int k = 0; k < MoveCount; k++)
      //////////         {
      //////////            List.Add(random.Next(0, BaseCube.CubeRotation.Length));
      //////////         }
      //////////         SolutionQueue.Enqueue(List);
      //////////      }

      //////////      //Threads Starten
      //////////      ResedFinished();
      //////////      foreach (ThreadedEvolutionaryCubexWorker cubexWorker in CubexWorker)
      //////////      {
      //////////         cubexWorker.Continue();
      //////////      }

      //////////      //Auf beendigung warten
      //////////      ResetEvent.Reset();
      //////////      ResetEvent.WaitOne();



      //////////      if (BestSolutionLength < OverAllSolutionLength)
      //////////      {
      //////////         OverAllSolutionLength = BestSolutionLength;
      //////////         PreSolutionList.AddRange(BestSolution);
      //////////         MinMoves = 1;
      //////////         MaxMoves = 7;
      //////////         //if (BackTrackingList.Count > 0)
      //////////         //{
      //////////         //   Console.WriteLine("Backtracking Successful");
      //////////         //   btMin = 1;
      //////////         //   btMax = 5;
      //////////         //}

      //////////         ////BackTrackingList.Clear();
      //////////         //if(btPoints.Count>0)
      //////////         //   Debug.WriteLine("BT Successful");

      //////////      }
      //////////      else
      //////////      {
      //////////         //Add Current Solution to Backtracking List
      //////////         //if (OverAllSolutionLength < BaseSolution)
      //////////         //{
      //////////         //   if (btPoints.Count > 0 && btPoints[0].SolutionLength <= OverAllSolutionLength)
      //////////         //   {
      //////////         //      OverAllSolutionLength = btPoints[0].SolutionLength;
      //////////         //      PreSolutionList.Clear();
      //////////         //      PreSolutionList.AddRange(btPoints[0].SolutionSteps);
      //////////         //      Debug.WriteLine("BT didn't improve Solution");
      //////////         //   }
      //////////         //   else
      //////////         //   {
      //////////         //      Debug.WriteLine("Seting BT Point" + ((btPoints.Count>0)?" BT improved Solution!":""));
      //////////         //      btPoints.Clear();
      //////////         //      btPoints.Add(new BacktrackingPoint
      //////////         //                      {
      //////////         //                         SolutionLength = OverAllSolutionLength,
      //////////         //                         SolutionSteps = new List<int>(PreSolutionList)
      //////////         //                      });
      //////////         //   }
      //////////         //}

      //////////         ////Reset OverAllSolutionLength
      //////////         //OverAllSolutionLength = BaseSolution;

      //////////         ////Step Back by Removing some Steps
      //////////         //int BombLen = random.Next(Math.Min(PreSolutionList.Count, btMin), Math.Min(PreSolutionList.Count, btMax));
      //////////         //int BombStart = Math.Max(PreSolutionList.Count - BombLen, 0);
      //////////         ////BackTrackingList.AddRange(PreSolutionList.GetRange(BombStart, BombLen));
      //////////         //PreSolutionList.RemoveRange(BombStart, BombLen);




      //////////         //Console.WriteLine("Backtracking Active");
      //////////         //if (BackTrackingList.Count > 0)
      //////////         //{
      //////////         //   PreSolutionList.AddRange(BackTrackingList);
      //////////         //   BackTrackingList.Clear();
      //////////         //   btMin += 2;
      //////////         //   btMax += 2;
      //////////         //}
      //////////         //int BombLen = random.Next(Math.Min(PreSolutionList.Count,btMin), Math.Min(PreSolutionList.Count, btMax));
      //////////         //int BombStart = Math.Max(PreSolutionList.Count - BombLen - 1,0);
      //////////         //BackTrackingList.AddRange(PreSolutionList.GetRange(BombStart,BombLen));
      //////////         //PreSolutionList.RemoveRange(BombStart, BombLen);
      //////////      }

      //////////      InvokeOnStatusChanged((float)(j + 1) / (float)next * 100f, OverAllSolutionLength);
      //////////   }



      //////////   //Recover Bombed List if no Better solution was found
      //////////   //if (btPoints.Count > 0 && btPoints[0].SolutionLength < OverAllSolutionLength)
      //////////   //{
      //////////   //   OverAllSolutionLength = btPoints[0].SolutionLength;
      //////////   //   PreSolutionList.Clear();
      //////////   //   PreSolutionList.AddRange(btPoints[0].SolutionSteps);
      //////////   //   Debug.WriteLine("BT didn't improve Solution");
      //////////   //}

      //////////   Cubex solutionCube = new Cubex();
      //////////   PrepareCube(BaseCube, solutionCube, PreSolutionList);
      //////////   int SolutionLen = SolveCube(solutionCube, PreSolutionList.Count);
      //////////   float SolutionImprovement = SolutionLen - BaseSolution;

      //////////   InvokeOnSetSolution(PreSolutionList, SolutionLen, SolutionImprovement);
      //////////   //PrepareCube(BaseCube, solutionCube, PreSolutionList);
      //////////   //      Solution = RandomMoves(MinMoves, MaxMoves, solutionCube);
      //////////   //      SolutionLen = SolveCube(solutionCube, PreSolutionList.Count);

      //////////   //      if (SolutionLen < BestSolutionLen)
      //////////   //      {
      //////////   //         BestSolution = Solution;
      //////////   //         BestSolutionLen = SolutionLen;
      //////////   //      }
      //////////   //   }
      //////////   //if (BestSolutionLen < OverAllBestSolutionLen)
      //////////   //{
      //////////   //   PreSolutionList.AddRange(BestSolution);
      //////////   //   OverAllBestSolutionLen = BestSolutionLen;
      //////////   //   MinMoves = 1;
      //////////   //   MaxMoves = 4;
      //////////   //}
      //////////   //else if (++NoImprovementCount > 20)
      //////////   //{
      //////////   //   NoImprovementCount = 0;
      //////////   //   MinMoves += 2;
      //////////   //   MaxMoves += 2;
      //////////   //}

      //////////   //PrepareCube(BaseCube, solutionCube, PreSolutionList);
      //////////   //SolutionImprovement = SolveCube(solutionCube, PreSolutionList.Count) - BaseSolution;
      //////////   lock (this)
      //////////   {
      //////////      IsActive = false;
      //////////   }
      //////////}

      private bool interrupt = false;
      public void Interrupt()
      {
         lock (this)
         {
            interrupt = true;
            SolutionQueue.Clear();
         }
      }
      private bool IsActive = false;
      public bool EvaluateSolutions()
      {
         if (MainWorkerThread != null && MainWorkerThread.IsAlive)
            return false;

         interrupt = false;
         MainWorkerThread = new Thread(EvaluateSolution);
         MainWorkerThread.Start();
         ResetEvent.Set();
         return true;
      }

      //public List<int> EvaluateSolutionsThreaded(out int SolutionImprovement)
      //{
      //   for (int i = 0; i < 100; i++)
      //   {
      //      var List = new List<int>();
      //      int count = random.Next(1, 4);
      //      for (int j = 0; j < count; j++)
      //      {
      //         List.Add(random.Next(0, BaseCube.CubeRotation.Length));
      //      }
      //      SolutionQueue.Enqueue(List);
      //   }

      //   ResedFinished();
      //   foreach (ThreadedEvolutionaryCubexWorker cubexWorker in CubexWorker)
      //   {
      //      cubexWorker.Continue();
      //   }


      //   SolutionImprovement = 0;
      //   return new List<int>();
      //}

      private int FinishedThreads = 0;

      private void ThreadFinished()
      {
         lock (this)
         {
            FinishedThreads++;
            if (FinishedThreads == CubexWorker.Length)
               ResetEvent.Set();
         }
      }

      private void ResedFinished()
      {
         lock (this)
         {
            FinishedThreads = 0;
         }
      }

      private float BestSolutionLength = float.MaxValue;
      private int[] BestSolution;

      private void ThreadOnSetSolution(ThreadedEvolutionaryCubexWorker Sender, List<int> Solution, int SolutionLength, float KukaMoves)
      {
         lock (this)
         {
            SolutionsCalculated++;
            //SolutionList.Add(Solution, SolutionLength);
            //if (SolutionLength < BestSolutionLength)
            //{
            //   BestSolution = Solution.ToArray();
            //   BestSolutionLength = SolutionLength;
            //}
            Solution.InsertRange(0,CurrentElement.Solution);
            if (KukaMoves < CurrentElement.Fitness)
            {
               SolutionsToCalc += 20;
               if(CurrentElement.Childs.ContainsKey(KukaMoves))
               {
                  //Kind ersetzen, falls die getätigten moves weniger sind
                  if (CurrentElement.Childs[KukaMoves].Solution.Count > Solution.Count)
                  {
                     CurrentElement.Childs[KukaMoves].Solution.Clear();
                     CurrentElement.Childs[KukaMoves].Solution.AddRange(Solution);
                  }
               }
               else
               {
                  CurrentElement.Childs.Add(KukaMoves,new BTElement(CurrentElement)
                                                         {
                                                            Fitness = KukaMoves,
                                                            Solution = new List<int>(Solution)
                                                         });
               }
            }
            if (KukaMoves < OverAllSolutionLength)
            {
               OverAllSolutionLength = KukaMoves;
               OverAllSolution.Clear();
               OverAllSolution.AddRange(Solution);
            }


            InvokeOnStatusChanged((float)SolutionsCalculated / (float)SolutionsToCalc * 100f, OverAllSolutionLength);
            //SolutionList.Add(Solution, KukaMoves);
            //if (KukaMoves < BestSolutionLength)
            //{
            //   BestSolution = Solution.ToArray();
            //   BestSolutionLength = KukaMoves;
            //}

            if (SolutionQueue.Count > 0)
               Sender.Continue();
            else
               ThreadFinished();
         }
      }

      private bool OnRequestMoves(ThreadedEvolutionaryCubexWorker Sender, out List<int> SolutionList)
      {
         SolutionList = null;
         lock (this)
         {
            if (SolutionQueue.Count > 0)
            {
               SolutionList = SolutionQueue.Dequeue();
               return true;
            }
            return false;
         }
      }

      
      private void PrepareCube(Cubex BaseCube, List<int> PreSolution)
      {
         foreach (var worker in CubexWorker)
         {
            worker.PrepareCube(BaseCube, PreSolution);
         }
      }
      private void PrepareCube(Cubex BaseCube, Cubex PreparedCube, List<int> PreSolution)
      {
         BaseCube.CopyTo(PreparedCube);
         foreach (var i in PreSolution)
         {
            PreparedCube.CubeRotation[i]();
         }
      }

      private int SolveCube(Cubex Cube)
      {
         return SolveCube(Cube, 0);
      }

      private int SolveCube(Cubex Cube, int BaseSteps)
      {
         Cube.SolveCube();
         return Cube.Solution().Count + BaseSteps;
      }

      private int[] RandomMoves(int MinMoves, int MaxMoves, Cubex cubex)
      {
         int resCnt = random.Next(MinMoves, MaxMoves);
         var result = new int[resCnt];
         for (int i = 0; i < result.Length; i++)
         {
            result[i] = RandomMove(cubex);
         }
         return result;
      }

      private int RandomMove(Cubex cubex)
      {
         int result = random.Next(0, cubex.CubeRotation.Length);
         cubex.CubeRotation[result]();
         return result;
      }

      #region Nested type: BacktrackingList

      public class BacktrackingList : SortedList<float, List<int>>
      {
         public List<int> AtIndex(int Index)
         {
            int Start = 0;
            foreach (var pair in this)
            {
               if (Start++ == Index)
                  return pair.Value;
            }
            throw new IndexOutOfRangeException();
         }
         public float KeyAtIndex(int Index)
         {
            int Start = 0;
            foreach (var pair in this)
            {
               if (Start++ == Index)
                  return pair.Key;
            }
            throw new IndexOutOfRangeException();
         }
         public void RemoveAll(int StartIndex)
         {
            while (Count > StartIndex)
            {
               Remove(KeyAtIndex(Count - 1));
            }
         }
      }

      #endregion

      #region Nested type: BacktrackingPoint

      public class BacktrackingPoint
      {
         public float SolutionLength;
         public List<int> SolutionSteps = new List<int>();
         public BacktrackingList BackTrackingList = new BacktrackingList();
      }

      public class BTElement
      {
         public BTElement()
         {
            Childs = new BTChildList();
            Evaluated = false;
            Solution = new List<int>();
         }
         public BTElement(BTElement Parent): this()
         {
            this.Parent = Parent;
         }
         public BTElement Parent { get; set; }
         public BTChildList Childs { get; set; }
         public float Fitness { get; set; }
         public List<int> Solution { get; set; }
         public bool Evaluated { get; set; }
      }
      public class BTChildList : SortedList<float, BTElement>
      {
         public BTElement AtIndex(int Index)
         {
            int Start = 0;
            foreach (var pair in this)
            {
               if (Start++ == Index)
                  return pair.Value;
            }
            throw new IndexOutOfRangeException();
         }
         public float KeyAtIndex(int Index)
         {
            int Start = 0;
            foreach (var pair in this)
            {
               if (Start++ == Index)
                  return pair.Key;
            }
            throw new IndexOutOfRangeException();
         }
         public void RemoveAll(int StartIndex)
         {
            while (Count > StartIndex)
            {
               Remove(KeyAtIndex(Count - 1));
            }
         }
      }

      #endregion
   }
   
}